//
// Created by Administrator on 2024-4-12
// 链表反转
//https://zhuanlan.zhihu.com/p/687410152
//

#include <iostream>

using namespace std;

struct Node
{
    int value;
    Node *next;
};


void printLinkedList(Node *h)
{
    Node *cur = h->next;
    while (cur)
    {
        cout << cur->value << ' ';
        cur = cur->next;
    }
    cout << endl;
}

// 用3个指针反转
Node *reverse01(Node *h)
{
    if (h == nullptr || h->next == nullptr)
        return h;
    Node *pre = nullptr;
    Node *cur = h->next;
    Node *end = cur->next;
    while (true)
    {
        cur->next = pre;
        if (end==nullptr)
            break;
        pre = cur;
        cur = end;
        end = end->next;
    }
    h = new Node{0,cur};
    return h;

}

// 用2个指针反转
Node *reverse02(Node *h)
{
    Node *pre = nullptr;
    Node *cur = nullptr;
    while (h != nullptr)
    {
        cur = h->next;
        h->next = pre;
        pre = h;
        h = cur;
    }
    Node *newHead = new Node{0, pre};
    return newHead;
}

int main()
{
//    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int arr[] = {1, 2, 3};
    Node *head = new Node();
    Node *cur = head;
    for (int i : arr)
    {
        Node *t = new Node{i, NULL};
        cur->next = t;
        cur = cur->next;
    }
    // 打印链表
    printLinkedList(head);
    head = reverse01(head);
    printLinkedList(head);
    return 0;
}